package cxydmmszl.chapter04.t076;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * <li style="color: red;">Prob</li>
 * N 皇后问题
 * <li style="color: green;">Desc</li>
 * N 皇后问题是指在 N*N 的棋盘上要摆 N 个皇后，要求
 * 任何两个皇后不同行，不同列也不再同一条斜线上，
 * 求给一个整数n，返回n皇后的摆法。
 * <li style="color: green;">Input</li>
 * 输入一个整数，代表 n(1<=n<=14)。
 * <li style="color: green;">Output</li>
 * 输出一个整数，代表 n 皇后的种数。
 * <li style="color: blue;">Link</li> CD94
 *
 * @author habitplus
 * @since 2021-09-23 14:42
 */
public class Main {
    static int[] rr = {1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        br.close();

//        if (n > 0 && n < 15) {
//            System.out.println(rr[n - 1]);
//        } else {
//            System.out.println(0);
//        }

        int num = queen2(n);
        System.out.println(num);
    }

    private static int queen2(int n) {
        if (n < 1 || n > 32) return 0;

        int upperLim = n == 32 ? -1 : (1 << n) - 1;
        return queen2(upperLim, 0, 0, 0);
    }

    private static int queen2(int upperLim, int colLim, int leftDiaLim, int rightDiaLim) {
        if (colLim == upperLim) {
            return 1;
        }

        int pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));
        int res = 0;
        int mostRightOne;
        while (pos != 0) {
            mostRightOne = pos & (~pos + 1);
            pos = pos - mostRightOne;
            res += queen2(upperLim, colLim | mostRightOne,
                    (leftDiaLim | mostRightOne) << 1,
                    (rightDiaLim | mostRightOne) >>> 1);
        }
        return res;
    }

    private static int queen1(int n) {
        if (n <= 0) return 0;

        // 第 i 个 皇后放在第 i 行，所在的列
        int[] col = new int[n];
        return recur(0, n, col);

    }

    private static int recur(int i, int n, int[] col) {
        // 找到一种可行的放置方法
        if (i == n) return 1;

        int res = 0;

        for (int j = 0; j < n; j++) {
            // 判断当前列是否能放置
            if (place(i, j, col)) {
                col[i] = j;
                res += recur(i + 1, n, col);
            }
        }

        return res;
    }

    // 第 i 个皇后 是否能放置在第 j 列
    private static boolean place(int i, int j, int[] col) {
        for (int k = 0; k < i; k++) {
            // 不能在同一列，同一对角线上
            if (j == col[k] || Math.abs(col[k] - j) == Math.abs(k - i)) {
                return false;
            }
        }
        return true;
    }
}
